Reverse linked list

Time: O(N); Space: O(1); easy

Reverse a singly linked list.

Example 1:

Input: head = {ListNode} 1->2->3->4->5->None

Output: {ListNode} 5->4->3->2->1->None

Follow up:

  • A linked list can be reversed either iteratively or recursively. Could you implement both?

[1]:

class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

    def __repr__(self):
        if self:
            return "{} -> {}".format(self.val, repr(self.next))

1. Iterative solution [O(N, O(1)]

[2]:

class Solution1(object):
    """
    Time: O(N)
    Space: O(1)
    """
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        dummy = ListNode(float("-inf"))

        while head:
            dummy.next, head.next, head = head, dummy.next, head.next

        return dummy.next

[4]:

s = Solution1()
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
res = s.reverseList(head)

exp = [5,4,3,2,1]
for val in exp:
    assert res.val == val
    res = res.next

2. Recursive solution [O(N), O(N)]

[5]:

class Solution2(object):
    """
    Time: O(N)
    Space: O(N)
    """
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        [begin, end] = self.reverseListRecu(head)
        return begin

    def reverseListRecu(self, head):
        if not head:
            return [None, None]

        [begin, end] = self.reverseListRecu(head.next)

        if end:
            end.next = head
            head.next = None
            return [begin, head]
        else:
            return [head, head]

[7]:

s = Solution2()
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
res = s.reverseList(head)

exp = [5,4,3,2,1]
for val in exp:
    assert res.val == val
    res = res.next